package algorithm.segmentTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeSet;

public class FallingSquares {

    public static class SegmentTree {
        private int[] max;
        private int[] change;
        private boolean[] update;

        private int l;
        private int r;

        public SegmentTree(int N) {
            int num = N + 1;
            max = new int[num << 2];
            change = new int[num << 2];
            update = new boolean[num << 2];
            this.l = 1;
            this.r = N;
        }

        private void pushUp(int rt) {
            max[rt] = Math.max(max[rt << 1], max[rt << 1 | 1]);
        }

        private void pushDown(int rt) {
            if (update[rt]) {
                max[rt << 1] = change[rt];
                max[rt << 1 | 1] = change[rt];
                change[rt << 1] = change[rt];
                change[rt << 1 | 1] = change[rt];
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                update[rt] = false;
            }
        }

        public void update(int L, int R, int C) {
            updateProcess(L, R, C, this.l, this.r, 1);
        }

        private void updateProcess(int L, int R, int C, int l, int r, int rt) {
            if (L <= l && R >= r) {//范围全包，可以懒住了，无需下放了。
                max[rt] = C;
                change[rt] = C;
                update[rt] = true;
                return;
            }

            int mid = (l + r) >> 1;
            pushDown(rt);
            if (L <= mid)
                updateProcess(L, R, C, l, mid, rt << 1);
            if (R > mid)
                updateProcess(L, R, C, mid + 1, r, rt << 1 | 1);
            pushUp(rt);
        }

        public int query(int L, int R) {
            return queryProcess(L, R, this.l, this.r, 1);
        }

        private int queryProcess(int L, int R, int l, int r, int rt) {
            if (L <= l && R >= r) {
                return max[rt];
            }

            int mid = (l + r) >> 1;
            pushDown(rt);
            int max = Integer.MIN_VALUE;
            if (L <= mid)
                max = Math.max(max, queryProcess(L, R, l, mid, rt << 1));
            if (R > mid)
                max = Math.max(max, queryProcess(L, R, mid + 1, r, rt << 1 | 1));
            return max;
        }

    }

    public HashMap<Integer, Integer> getIndex(int[][] positions) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int[] position : positions) {
            treeSet.add(position[0]);
            treeSet.add(position[0] + position[1] - 1);
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (Integer position : treeSet) {
            map.put(position, ++count);
        }
        return map;
    }

    public List<Integer> fallingSquares(int[][] positions) {
        HashMap<Integer, Integer> map = getIndex(positions);
        ArrayList<Integer> list = new ArrayList<>();
        SegmentTree segmentTree = new SegmentTree(map.size());
        int max = 0;
        for (int[] position : positions) {
            int height = segmentTree.query(map.get(position[0]), map.get(position[0] + position[1] - 1));
            max = Math.max(max, height + position[1]);
            list.add(max);
            segmentTree.update(map.get(position[0]), map.get(position[0] + position[1] - 1), height + position[1]);
        }
        return list;
    }


    public static void main(String[] args) {
        int[][] position = {{9, 7}, {1, 9}, {3, 1}};
        List<Integer> list = new FallingSquares().fallingSquares(position);
        System.out.println(list);
    }

}
